Error correcting codes are ubiquitous in communications and data storage systems. Recently a considerable interest has grown in a class of codes known as low-density parity-check (LDPC) codes.
LDPC codes are well represented by bipartite graphs, often called Tanner graphs, in which one set of nodes, the variable nodes, corresponds to bits of the codeword and the other set of nodes, the constraint nodes, sometimes called check nodes, correspond to the set of parity-check constraints which define the code. Edges in the graph connect variable nodes to constraint nodes. A variable node and a constraint node are said to be neighbors if they are connected by an edge in the graph. For simplicity, we generally assume that a pair of nodes is connected by at most one edge. To each variable node is associated one bit of the codeword. In some cases some of these bits might be punctured, i.e., removed from the codeword. For simplicity we shall generally assume that no puncturing is used.
A bit sequence associated one-to-one with the variable node sequence is a codeword of the code if and only if, for each constraint node, the bits neighboring the constraint (via their association with variable nodes) sum to zero modulo two, i.e., they comprise an even number of ones.
The decoders and decoding algorithms used to decode LDPC codewords operate by exchanging messages within the graph along the edges and updating these messages by performing computations at the nodes based on the incoming messages. Such algorithms will be generally referred to as message passing algorithms. Each variable node in the graph is initially provided with a soft bit, termed a received value, that indicates an estimate of the associated bit's value as determined by observations from, e.g., the communications channel. Ideally, the estimates for separate bits are statistically independent. This ideal can be, and often is, violated in practice. A collection of received values constitutes a received word. For purposes of this application we may identify the signal observed by, e.g., the receiver in a communications system, with the received word.
The number of edges attached to a node, i.e., a variable node or constraint node, is referred to as the degree of the node. A regular graph or code is one for which all variable nodes have the same degree, j say, and all constraint nodes have the same degree, k say. In this case we say that the code is a (j,k) regular code. These codes were originally invented by Gallager (1961). In contrast to a “regular” code, an irregular code has constraint nodes and/or variable nodes of differing degrees. For example, some variable nodes may be of degree 4, others of degree 3 and still others of degree 2.
While irregular codes can be more complicated to represent and/or implement, it has been shown that irregular LDPC codes can provide superior error correction/detection performance when compared to regular LDPC codes.
In order to more precisely describe the decoding process we introduce the notion of a socket in describing LDPC graphs. A socket can be interpreted as an association of an edge in the graph to a node in the graph. Each node has one socket for each edge attached to it and the edges are “plugged into” the sockets. Thus, a node of degree d has d sockets attached to it. If the graph has L edges then there are L sockets on the variable node side of the graph, called the variable sockets, and L sockets on the constraint node side of the graph, called the constraint sockets. For identification and ordering purposes, the variable sockets may be enumerated 1, . . . , L so that variable sockets attached to one variable node appear contiguously. In such a case, if the first three variable nodes have degrees d1, d2, and d3 respectively, then variable sockets 1, . . . , d1 are attached to the first variable node, variable sockets d1+1, . . . , d1+d2 are attached to the second variable node, and variable sockets d1+d2+1, . . . , d1+d2+d3 are attached to the third variable node. Constraint node sockets may be enumerated similarly 1, . . . , L with constraint sockets attached to one constraint node appearing contiguously. An edge can be viewed as a pairing of sockets, one of each pair coming from each side of the graph. Thus, the edges of the graph represent an interleaver or permutation on the sockets from one side of the graph, e.g., the variable node side, to the other, e.g., the constraint node side. The permutations associated with these systems are often complex.
An exemplary bipartite graph 100 determining a (3,6) regular LDPC code of length ten and rate one-half is shown in FIG. 1. Length ten indicates that there are ten variable nodes V1-V10, each identified with one bit of the codeword X1-X10 (and no puncturing in this case), generally identified by reference numeral 102. Rate one half indicates that there are half as many check nodes as variable nodes, i.e., there are five check nodes C1-C5 identified by reference numeral 106. Rate one half further indicates that the five constraints are linearly independent, as discussed below. Each of the lines 104 represents an edge, e.g., a communication path or connection, between the check nodes and variable nodes to which the line is connected. Each edge identifies two sockets, one variable socket and one constraint socket. Edges can be enumerated according to their variable sockets or their constraint sockets. The variable sockets enumeration corresponds to the edge ordering (top to bottom) as it appears on the variable node side at the point where they are connected to the variable nodes. The constraint sockets enumeration corresponds to the edge ordering (top to bottom) as it appears on the constraint node side at the point they are connected to the constraint nodes. During decoding, messages are passed in both directions along the edges. Thus, as part of the decoding process messages are passed along an edge from a constraint node to a variable node and vice versa.
An alternative to using a graph to represent codes is to use a matrix representation such as that shown in FIG. 2. In the matrix representation of a code, the matrix H 202, commonly referred to as the parity check matrix, includes the relevant edge connection, variable node and constraint node information. For simplicity we assume that at most one edge connects any pair of nodes. In the matrix H, each column corresponds to one of the variable nodes while each row corresponds to one of the constraint nodes. Since there are 10 variable nodes and 5 constraint nodes in the exemplary code, the matrix H includes 10 columns and 5 rows. The entry of the matrix corresponding to a particular variable node and a particular constraint node is set to 1 if an edge is present in the graph, i.e., if the two nodes are neighbors, otherwise it is set to 0. For example, since variable node V1 is connected to constraint node C1 by an edge, a one is located in the uppermost left-hand corner of the matrix 202. However, variable node V4 is not connected to constraint node C1 so a 0 is positioned in the fourth position of the first row of matrix 202 indicating that the corresponding variable and constraint nodes are not connected. We say that the constraints are linearly independent if the rows of H are linearly independent vectors over GF[2]. Enumerating edges by sockets, variable or constraint, corresponds to enumerating the 1's in H. Variable socket enumeration corresponds to enumerating top to bottom within columns and proceeding left to right from column to column, as shown in matrix 208. Constraint socket enumeration corresponds to enumerating left to right across rows and proceeding top to bottom from row to row, as shown in matrix 210.
In the case of a matrix representation, the codeword X which is to be transmitted can be represented as a vector 206 which includes the bits X1-Xn of the codeword to be processed. A bit sequence X1-Xn is a codeword if and only if the product of the matrix 206 and 202 is equal to zero, that is: Hx=0.
In the context of discussing codewords associated to LDPC graphs, it should be appreciated that in some cases the codeword may be punctured. Puncturing is the act of removing bits from a codeword to yield, in effect, a shorter codeword. In the case of LDPC graphs this means that some of the variable nodes in the graph correspond to bits that are not actually transmitted. These variable nodes and the bits associated with them are often referred to as state variables. When puncturing is used, the decoder can be used to reconstruct the portion of the codeword which is not physically communicated over a communications channel. Where a punctured codeword is transmitted the receiving device may initially populate the missing received word values (bits) with ones or zeros assigned, e.g., in an arbitrary fashion, together with an indication (soft bit) that these values are completely unreliable, i.e., that these values are erased. For simplicity, we shall assume that, when used, these receiver-populated values are part of the received word which is to be processed.
Consider for example the system 350 shown in FIG. 3. The system 350 includes an encoder 352, a decoder 357 and a communication channel 356. The encoder 350 includes an encoding circuit 353 that processes the input data A to produce a codeword X. The codeword X includes, for the purposes of error detection and/or correction, some redundancy. The codeword X may be transmitted over the communications channel. Alternatively, the codeword X can be divided via a data selection device 354 into first and second portions X′, X″ respectively by some data selection technique. One of the codeword portions, e.g., the first portion X′, may then be transmitted over the communications channel to a receiver including decoder 357 while the second portion X″ is punctured. As a result of distortions produced by the communications channel 356, portions of the transmitted codeword may be lost or corrupted. From the decoder's perspective, punctured bits may be interpreted as lost.
At the receiver soft bits are inserted into the received word to take the place of lost or punctured bits. The inserted soft bits indicate erasure of X″ bits and/or bits lost in transmission.
The decoder 357 will attempt to reconstruct the full codeword X from the received word Y and any inserted soft bits, and then perform a data decoding operation to produce A from the reconstructed codeword X.
The decoder 357 includes a channel decoder 358, e.g., an LDPC decoder, for reconstructing the complete codeword X from the received word Y and any inserted soft bits. In addition it includes a data decoder 359 for removing the redundant information included in the codeword to produce the original input data A from the reconstructed codeword X.
It will be appreciated that received words generated in conjunction with LDPC coding, can be processed by performing LDPC decoding operations thereon, e.g., error correction and detection operations, to generate a reconstructed version of the original codeword. The reconstructed codeword can then be subject to data decoding to recover the original data that was coded. The data decoding process may be, e.g., simply selecting a specific subset of the bits from the reconstructed codeword.
As mentioned above, LDPC decoding operations generally comprise message passing algorithms. There are many potentially useful message passing algorithms and the use of such algorithms is not limited to LDPC decoding. As will be discussed in detail below, the current invention is directed to methods and apparatus which provide a simple, e.g., low hardware complexity, implementation of an decoder algorithm that gives very good and often near optimal performance in many circumstances. The proposed algorithm can be viewed as an approximation of the well-known belief propagation algorithm.
To facilitate understanding of the invention discussed in the sections which follow, we will now give a brief mathematical description of belief propagation.
Belief propagation for (binary) LDPC codes can be expressed as follows. Messages transmitted along the edges of the graph are interpreted as log-likelihoods
  log  ⁢          ⁢            p      0              p      1      for the bit associated to the variable node. Here, (p0,p1) represents a conditional probability distribution on the associated bit where px denotes the probability that the bit takes the value x. The soft bits provided to the decoder by the receiver are also given in the form of a log-likelihood. Thus, the received values, i.e., the elements of the received word, are log-likelihoods of the associated bits conditioned on the observation of the bits provided by the communication channel. In general, a message m represents the log-likelihood m and a received value y represents the log-likelihood y. For punctured bits the log-likelihood received value y is set to 0, indicating
      p    0    =            p      1        =          1      /      2.      
Let us consider the message-passing rules of belief propagation. Messages are denoted by mC2V for messages from check nodes to variable nodes and by mV2C for messages from variable nodes to check nodes. Consider a variable node with d edges. For each edge j=1, . . . , d let mC2V (i) denote the incoming message on edge i. At the initialization of the decoding process we set mC2V=0 for every edge. In general, outgoing messages from variable nodes are given by
            m              V        ⁢                                  ⁢        2        ⁢        C              ⁡          (      j      )        =      y    +          (                        ∑                      i            =            1                    d                ⁢                              m                          C              ⁢                                                          ⁢              2              ⁢              V                                ⁡                      (            i            )                              )        -                            m                      C            ⁢                                                  ⁢            2            ⁢            V                          ⁡                  (          j          )                    .      The outgoing decoded soft value from a node (not an edge message) corresponding to this operation is given by
      x    out    =      y    +                  (                              ∑                          i              =              1                        d                    ⁢                                    m                              C                ⁢                                                                  ⁢                2                ⁢                V                                      ⁡                          (              i              )                                      )            .      The outgoing hard decision associated to this output is obtained from the sign of Xout.
At the check nodes it is often more convenient to represent the messages using their ‘sign’ and magnitudes. Thus, for a message m let mp∈GF[2] denote the ‘parity’ of the message, i.e., mp=0 if m≧0 and mp=1 if m<0. Additionally let mr∈[0,∞] denote the magnitude of m. Thus, we have m=−1mpmr. At the check node the updates for mp and mr are separate. We have, for a check node of degree d,
                    m        p        C2V            ⁡              (        j        )              =                  (                              ∑                          i              =              1                        d                    ⁢                                    m              p                              V                ⁢                                                                  ⁢                2                ⁢                C                                      ⁡                          (              i              )                                      )            -                        m          p                      V            ⁢                                                  ⁢            2            ⁢            C                          ⁡                  (          j          )                      ,
where all addition is over GF[2], and
            m      r              C        ⁢                                  ⁢        2        ⁢        V              ⁡          (      j      )        =            F              -        1              ⁡          (                        (                                    ∑                              i                =                1                            d                        ⁢                          F              ⁡                              (                                                      m                    r                                          V                      ⁢                                                                                          ⁢                      2                      ⁢                      C                                                        ⁡                                      (                    i                    )                                                  )                                              )                -                  F          ⁡                      (                                          m                r                                  V                  ⁢                                                                          ⁢                  2                  ⁢                  C                                            ⁡                              (                j                )                                      )                              )      where we define F(x):=ln coth (x/2). In both of the above equations the superscript V2C denotes the incoming messages at the constraint node. We note that F is its own inverse, i.e., F−1(x)=F(x).